﻿<!DOCTYPE html>
<html>

<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Openmp实现求矩阵元素最大值</title>
  <link rel="stylesheet" href="https://stackedit.io/style.css" />
</head>

<body class="stackedit">
  <div class="stackedit__html"><h1 id="openmp实现求矩阵元素最大值">Openmp实现求矩阵元素最大值</h1>
<p><strong>计试61 张翀 2140506063</strong></p>
<h2 id="题目">题目</h2>
<p>Create a program that computes the sum of all the elements in an array A (in fortran or C/C++) or a program that finds the largest number in an array A (Fortran) . Use OpenMP directives to make it run in parallel</p>
<h2 id="思路">思路</h2>
<p>首先求每一行的最大值，再在这些最大值中取最大值。其中，求每一行的最大值操作是独立的，可以并行执行。</p>
<h2 id="代码">代码</h2>
<p>核心命令：<code>#pragma omp parallel for num_threads(num_threads)</code><br>
这条命令的含义是，紧跟代码的for循环被多个线程并行执行，线程数由参数<code>num_threads</code>确定。在两层for循环中，第一层的含义是各行依次求最大值，这个过程可以并行执行；第二层的含义是逐个比较元素而获得最大值，这个过程是串行过程。因此，应该并行第一层for循环。<br>
为方便测试时间，设计函数<code>matGene</code>生成指定大小的矩阵，<code>vecGene</code>生成指定大小的向量，生成矩阵之后求乘积，再输出结果。设计代码如附件所示。</p>
<h2 id="实验结果">实验结果</h2>
<p>使用如下命令编译并执行：<code>g++ -fopenmp main.cpp &amp;&amp; ./a.out mat_dim num_threads</code>，执行可执行文件时带的两个参数分别是矩阵维度和使用的线程数。<br>
测试时间如下：</p>

<table>
<thead>
<tr>
<th align="center">线程数</th>
<th align="center">1</th>
<th align="center">2</th>
<th align="center">并行加速比</th>
</tr>
</thead>
<tbody>
<tr>
<td align="center">256</td>
<td align="center">0.0002887</td>
<td align="center">0.0002335</td>
<td align="center">1.2364</td>
</tr>
<tr>
<td align="center">512</td>
<td align="center">0.0007073</td>
<td align="center">0.0007808</td>
<td align="center">0.9059</td>
</tr>
<tr>
<td align="center">1024</td>
<td align="center">0.0034686</td>
<td align="center">0.0018217</td>
<td align="center">1.9040</td>
</tr>
<tr>
<td align="center">2048</td>
<td align="center">0.0134514</td>
<td align="center">0.0074485</td>
<td align="center">1.8059</td>
</tr>
<tr>
<td align="center">4096</td>
<td align="center">0.0540589</td>
<td align="center">0.0319176</td>
<td align="center">1.6937</td>
</tr>
</tbody>
</table><p>表格中最左侧一栏为测试时矩阵维度，表格中时间单位为秒。</p>
<p><img alt="矩阵求最值并行时间展示" src="https://gitee.com/WinterShiver/HPC/raw/master/OpenMP/2-matrix-max/2.png"></p>
<p>以上为程序运行时间的测试结果展示，为方便展示，横纵坐标均取对数。由图像可见两点：</p>
<ul>
<li>通过直线的大致斜率可见，求最大值的算法是O(n^2)的；</li>
<li>通过2线程并行执行程序，程序确实能获得近似为2的加速比；</li>
<li>因为在维度数较小时，最后一步无法线性化的操作占用总时间较长，所以此时的加速比较低。</li>
</ul>
</div>
</body>

</html>
